package 单链表;


import java.util.*;

public class ListNode {
    public int val;
    public ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
    //已经排序好的单链表 需要删除

    //最简单的就是set集合存储 然后删除  这样效率肯定是低的
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        if (head == null) {
            return null;
        }
        ListNode cur = head;
        ListNode pre = dummy;
        while (cur.next != null) {
            if (cur.val == cur.next.val) {
                while (cur.next != null && cur.val == cur.next.val) {
                    //相等了
                    cur = cur.next; //往下移动
                }
                //分情况讨论 如果是结尾的话 那么直接指向null
                if (cur.next == null) {
                    pre.next = null;
                } else {
                    //否则先保存下面的节点 再移动指针
                    ListNode curNext = cur.next;
                    pre.next = cur.next;
                    cur = curNext;
                }
            } else {
                cur = cur.next;
                pre = pre.next;
            }
        }
        return dummy.next;
    }

    public void reorderList(ListNode head) {
        // 数组是有下标的  如果能转换成数组的写法携带下标的样式，y那么就是没问题的
        List<ListNode> list = new ArrayList<>();
        ListNode temp = head;
        while (temp != null) {
            list.add(temp);
            temp = temp.next;
        }
        int i = 0;
        int j = list.size() - 1;
        while (i < j) {
            ListNode pre = list.get(i);
            ListNode next = list.get(j);
            pre.next = next;
            i++;
            if (i == j) {
                break;
            }
            pre = list.get(j);
            next = list.get(i);
            pre.next = next;
            j--;
        }
        //释放最后一个系欸但
        list.get(i).next = null;
    }

    //删除倒数第n个节点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 先移动快指针 然后移动慢指针
        if (head==null){
            return null;
        }
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode fast=head;
        ListNode slow=dummy;

        for (int i = 0; i < n; i++) {
            fast=fast.next;
        }
        while (fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        //删除倒数第n个节点
        slow.next=slow.next.next;
        //返回 dummy的next节点
        return  dummy.next;
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map=new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            char[] charArray = strs[i].toCharArray();
            Arrays.sort(charArray);
            String str=new String(charArray);
            List<String> list = map.getOrDefault(str, new ArrayList<>());
            list.add(strs[i]);
            map.put(str,list);
        }
        return  new ArrayList<>(map.values());
    }

    //最长连续序列
    public int longestConsecutive(int[] nums) {
        Set<Integer> set=new HashSet<>();
        for(int num:nums){
            set.add(num);
        }
        int maxLen=0;
        for(int num:set){
            int  numNext=num+1;
            int  longest=1;
            if (!set.contains(num-1)){
                while (set.contains(numNext)){
                    numNext++;
                    longest++;
                }
            }
            maxLen=Math.max(longest,maxLen);
        }
        return maxLen;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA==null||headB==null){
            return null;
        }
        Set<ListNode> set=new HashSet<>();

        ListNode p=headA;

        while (p!=null){
            set.add(p);
            p=p.next;
        }
        ListNode q=headB;
        while (q!=null){
            if (set.contains(q)){
                return q;
            }
            q=q.next;
        }
        //使用双指针的原理
        //a
        //       c     a+b+c    b+c+a
        //b

//        while (p!=q){
//            p = (p != null) ? p.next : headB;  // 你的代码
//            q = (q != null) ? q.next : headA;
//        }
//        return q;
        return  null;
    }

    public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode pre=null;
        ListNode cur=head;
        while (cur!=null) {
            ListNode nextNode = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nextNode;
        }
        return pre;
    }


    //回文链表
    public boolean isPalindrome(ListNode head) {
        //找到中间 然后反转 再比较？
         List<Integer> list =new ArrayList<>();
         ListNode cur=head;
         while (cur!=null){
             list.add(cur.val);
             cur=cur.next;
         }
         int l=0,r=list.size()-1;
         while (l<r){
             if (!list.get(l).equals(list.get(r))){
                 return  false;
             }
             l++;
             r--;
         }
         return  true;
    }

    public boolean hasCycle(ListNode head) {
      if (head==null||head.next==null){
          return false;
      }
      ListNode fast=head;
      ListNode slow=head;
      while (fast.next!=null&&fast.next.next!=null){
          fast=fast.next.next;
          slow=slow.next;
          if (fast==slow){
              return true;
          }
      }
      return false;
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
         if (list1==null){
             return list2;
         }
         if (list2==null){
             return list1;
         }
         ListNode p=list1;
         ListNode q=list2;
         ListNode dummy=new ListNode(0);
         ListNode cur=dummy;

         while (p!=null&&q!=null){
             if (p.val>=q.val){
                 cur.next=q;
                 q=q.next;
             }else {
                 cur.next = p;
                 p = p.next;
             }
             cur=cur.next;
         }
         cur.next=p!=null?p:q;
         return dummy.next;
    }
     //返回中序遍历的结果



}
